#!/usr/bin/env python3
# -*- coding: UTF-8 -*-

'''
文件名称：main.py
创 建 者：yang qiang
创建日期：2020年06月16日
版    本：v1.0.0
描    述：
Copyright (C) 2020 All rights reserved.
'''


class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: bool
        """

        record = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]

        for pre, cur in prerequisites:
            record[cur] += 1
            adjacency[pre].append(cur)

        count = numCourses
        queue = list()
        for i in range(numCourses):
            if record[i] == 0:
                queue.append(i)
                count -= 1
        
        while queue:
            for i in queue:
                queue.remove(i)
                for j in adjacency[i]:
                    record[j] -= 1
                    if record[j] == 0:
                        queue.append(j)
                        count -= 1

        return count == 0
